package com.ssh;

public class Trap_42 {
	public static void main(String[] args) {
		int[] height = {0,1,0,2,1,0,1,3,2,1,3,1};
		System.out.println(trap1(height));
	}
	public static int trap1(int[] height) {
		int max = 0,leftmax = 0,rightmax = 0,l = 0,r = height.length-1;
		while (l <= r) {
			leftmax = Math.max(leftmax, height[l]);
			rightmax = Math.max(rightmax, height[r]);
			if (leftmax < rightmax) {
				max += (leftmax-height[l]);
				l++;
			}else {
				max += (rightmax-height[r]);
				r--;
			}
		}
		return max;
	}
	public static int trap(int[] height) {
		int start = 0,end = height.length-1,sum = 0,max = 0;
		for (int i = 0; i < height.length; i++) {
			max = Math.max(height[i], max);
		}
		do {
			for (int i = start; i < height.length; i++) {
				if (height[i] > 0) {
					start = i;
					break;
				}
			}
			for (int i = end; i >= 0; i--) {
				if (height[i] > 0) {
					end = i;
					break;
				}
			}
			System.out.println(start);
			System.out.println(end);
			if (start == end) {
				break;
			}else {
				for (int i = start; i <= end; i++) {
					height[i] -= 1;
					System.out.println(i+"--"+height[i]);
				}
			}
			max--;
		}while(max > 0);
		for (int i = 0; i < height.length; i++) {
			if (height[i] < 0) {
				sum +=height[i];
			}
		}
		return -sum;
    }
}
